package Algorithom.sort;

import org.junit.Test;

/**
 * 快排
 * Created by svenl on 7/25/2017.
 */
public class QuickSort {

    /**
     *  快速排序
     * @param array 数组
     * @param i     起始点
     * @param j     终点
     * @return 中间点
     */
    public int quickSort(int array[], int i, int j) {


        int base = array[i];


        while (i < j) {

            //从右向左查找小于base的数来填充array[i]
            while (i < j && array[j] >= base) {
                j--;
            }
            if (i < j) {
                array[i] = array[j];  //将array[j]填到array[i]中,array[j]就形成了一个坑
                i++;
            }

            //从左到右找大于或等于base的数来填充array[j],array[i]又形成了新的坑
            while (i < j && array[i] <= base) {
                i++;
            }
            if (i < j) {
                array[j] = array[i];
                j--;
            }

        }
        //退出时,i=j,将base填入这个坑中
        array[i] = base;
        for (int i1 : array) {
            System.out.print(i1+" ");
        }
        System.out.println( "i="+ i );
        //此时 array[i]左边都小于它,右边的都大于他
        return i;
    }

    /**
     * 快速排序入口
     * @param array
     * @param i
     * @param j
     */
    void
    quickSort1(int array[], int i, int j){
        if( i<j){
            int flag = quickSort(array,i,j);
            quickSort1(array,i,flag-1);
            quickSort1(array,flag+1,j );
        }
    }

    @Test
    public void QucikSortTest() {
        int[] array = new int[]{48, 6, 88, 60, 42, 83, 73, 88, 85};

        quickSort1(array,0,array.length -1);

        for (int i : array) {
            System.out.print( i+" " );
        }


    }

}
